#include "zhi.h"
//创建新map对象
map对象S* 新建map对象(虚拟机* 虚拟机S) {
   map对象S* objMap = 分配指定类型的内存块M(虚拟机S, map对象S);
   初始化对象头(虚拟机S, &objMap->objHeader, 对象类型_散列数组, 虚拟机S->mapClass);
   objMap->数组容量 = objMap->count = 0;
   objMap->entries = NULL;
   return objMap;
}

//计算数字的哈希码
static uint32_t 计算数字的哈希码(double num) {
   位64S bits64;
   bits64.num = num;
   return bits64.bits32[0] ^ bits64.bits32[1];
}

//计算对象的哈希码
static uint32_t 计算对象的哈希码(对象头S* objHeader) {
   switch (objHeader->type) {
      case 对象类型_类:  //计算class的哈希值
	 return 计算字符串哈希值(((Class*)objHeader)->name->value.start,
	       ((Class*)objHeader)->name->value.长度);
	       
      case 对象类型_范围: { //计算range对象哈希码
	 范围对象S* objRange = (范围对象S*)objHeader;
	 return 计算数字的哈希码(objRange->from) ^ 计算数字的哈希码(objRange->to);
      }
      case 对象类型_字符串:  //对于字符串,直接返回其hashCode
	 return ((字符串对象S*)objHeader)->hashCode;
      default:
	 runtime_错误("the hashable are objstring, objrange and class.");
   }
   return 0;
}

//根据value的类型调用相应的哈希函数
static uint32_t 根据值的类型调整调用相应的哈希函数(Value value) {
   switch (value.type) {
      case 值类型_假:
	 return 0;
      case 值类型_空:
	 return 1;
      case 值类型_数字:
	 return 计算数字的哈希码(value.num);
      case 值类型_真:
	 return 2;
      case 值类型_对象:
	 return 计算对象的哈希码(value.objHeader);
      default:
	 runtime_错误("unsupport type hashed!");
   }
   return 0;
}

//在entries中添加entry,如果是新的key则返回true
static bool 在entries中添加entry(Entry* entries, uint32_t 数组容量, Value key, Value value) {
   uint32_t index = 根据值的类型调整调用相应的哈希函数(key) % 数组容量;

  //通过开放探测法去找可用的slot
   while (true) {
      //找到空闲的slot,说明目前没有此key,直接赋值返回
      if (entries[index].key.type == 值类型_未定义) {
	 entries[index].key = key;
	 entries[index].value = value;
	 return true;	   //新的key就返回true
      } else if (是否相等(entries[index].key, key)) { //key已经存在,仅仅更新值就行
	 entries[index].value = value;
	 return false;	// 未增加新的key就返回false
      }

      //开放探测定址,尝试下一个slot
      index = (index + 1) % 数组容量;
   }
}

//使对象objMap的容量调整到newCapacity
static void 重新调整map的容量(虚拟机* 虚拟机S, map对象S* objMap, uint32_t newCapacity) {
   // 1 先建立个新的entry数组
   Entry* newEntries = 分配数组内存M(虚拟机S, Entry, newCapacity);
   uint32_t idx = 0;
   while (idx < newCapacity) {
      newEntries[idx].key = VT_TO_VALUE(值类型_未定义);
      newEntries[idx].value = VT_TO_VALUE(值类型_假);
      idx++;
   }

  // 2 再遍历老的数组,把有值的部分插入到新数组
   if (objMap->数组容量 > 0) {
      Entry* entryArr = objMap->entries;
      idx = 0;
      while (idx < objMap->数组容量) {
	 //该slot有值
	 if (entryArr[idx].key.type != 值类型_未定义) {
	    在entries中添加entry(newEntries, newCapacity,
		  entryArr[idx].key, entryArr[idx].value);
	 }
	 idx++;
      }
   }

   // 3 将老entry数组空间回收
   释放数组占用的内存M(虚拟机S, objMap->entries, objMap->count);
   objMap->entries = newEntries;     //更新指针为新的entry数组
   objMap->数组容量 = newCapacity;    //更新容量
}

//在objMap中查找key对应的entry
static Entry* 在map中查找key对应的entry(map对象S* objMap, Value key) {
   //objMap为空则返回null
   if (objMap->数组容量 == 0) {
      return NULL;
   }

//以下开放定址探测
//用哈希值对容量取模计算槽位(slot)
   uint32_t index = 根据值的类型调整调用相应的哈希函数(key) % objMap->数组容量;
   Entry* entry; 
   while (true) {
      entry = &objMap->entries[index];

      //若该slot中的entry正好是该key的entry,找到返回
      if (是否相等(entry->key, key)) {
	 return entry;
      }

      //key为VT_UNDEFINED且value为VT_TRUE表示探测链未断,可继续探测.
      //key为VT_UNDEFINED且value为VT_FALSE表示探测链结束,探测结束.
      if (VALUE_IS_UNDEFINED(entry->key) && VALUE_IS_FALSE(entry->value)) {
	 return NULL;    //未找到
      }

      //继续向下探测
      index = (index + 1) % objMap->数组容量;
   }
}

//在objMap中实现key与value的关联:objMap[key]=value
void 在map中实现key与value的关联(虚拟机* 虚拟机S, map对象S* objMap, Value key, Value value) {
   //当容量利用率达到80%时扩容
   if (objMap->count + 1 > objMap->数组容量 * MAP_LOAD_PERCENT) {
      uint32_t newCapacity = objMap->数组容量 * 容量增长因子M;
      if (newCapacity < 最小容量M) {
	 newCapacity = 最小容量M;
      }
      重新调整map的容量(虚拟机S, objMap, newCapacity);
   }

   //若创建了新的key则使objMap->count加1
   if (在entries中添加entry(objMap->entries, objMap->数组容量, key, value)) {
      objMap->count++;
   }
}

//从map中查找key对应的value: map[key]
Value 在map中查找key对应的value(map对象S* objMap, Value key) {
  Entry* entry = 在map中查找key对应的entry(objMap, key);
  if (entry == NULL) {
     return VT_TO_VALUE(值类型_未定义);
  }
  return entry->value;
}

//回收objMap.entries占用的空间
void 回收map中entry占用的空间(虚拟机* 虚拟机S, map对象S* objMap) {
   释放数组占用的内存M(虚拟机S, objMap->entries, objMap->count);
   objMap->entries = NULL;
   objMap->数组容量 = objMap->count = 0;
}

//删除objMap中的key,返回map[key]
Value 删除map中的key(虚拟机* 虚拟机S, map对象S* objMap, Value key) {
   Entry* entry = 在map中查找key对应的entry(objMap, key);

   if (entry == NULL) {
      return VT_TO_VALUE(值类型_空);
   }

//设置开放定址的伪删除
   Value value = entry->value;
   entry->key = VT_TO_VALUE(值类型_未定义); 
   entry->value = VT_TO_VALUE(值类型_真);   //值为真,伪删除

   if (VALUE_IS_OBJ(value)) {
      将obj作为临时根对象(虚拟机S, VALUE_TO_OBJ(value));
   }
   objMap->count--;  
   if (objMap->count == 0) { //若删除该entry后map为空就回收该空间
      回收map中entry占用的空间(虚拟机S, objMap);
   } else if (objMap->count < objMap->数组容量 / (容量增长因子M) * MAP_LOAD_PERCENT &&
	 objMap->count > 最小容量M) {   //若map容量利用率太低,就缩小map空间
      uint32_t newCapacity = objMap->数组容量 / 容量增长因子M;
      if (newCapacity < 最小容量M) {
	 newCapacity = 最小容量M;
      }
      重新调整map的容量(虚拟机S, objMap, newCapacity);
   }
   if (VALUE_IS_OBJ(value)) {
      去掉临时根对象(虚拟机S);
   }

  return value;
}
